/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._32_03;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._32_03
 * @ClassName: LevelOrder
 * @Author: linyaonan
 * @Date: 2020/3/30 17:38
 */
public class LevelOrder {
    public class MyTreeNode {
        public TreeNode treeNode;
        public int level;

        public MyTreeNode(TreeNode treeNode, int level) {
            this.treeNode = treeNode;
            this.level = level;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<MyTreeNode> nodes = new LinkedList<>();
        nodes.push(new MyTreeNode(root, 0));
        while (!nodes.isEmpty()) {
            MyTreeNode pop = nodes.poll();
            int level = pop.level;
            TreeNode treeNode = pop.treeNode;
            int size = result.size();
            if (size > level) {
                List<Integer> list = result.get(level);
                list.add(treeNode.val);
            } else {
                List<Integer> add = new ArrayList<>();
                add.add(treeNode.val);
                result.add(add);
            }
            level++;
            TreeNode left = treeNode.left;
            TreeNode right = treeNode.right;
            if (left != null) {
                nodes.add(new MyTreeNode(left, level));
            }
            if (right != null) {
                nodes.add(new MyTreeNode(right, level));
            }
        }
        for (int i = 0; i < result.size(); i++) {
            // 奇数行
            if (i % 2 != 0) {
                List<Integer> list = result.get(i);
                Collections.reverse(list);
            }
        }
        return result;
    }
}
